//
// Created by song on 16-12-30.
//

#ifndef C0COMPILER_DEFUSECHAIN_H
#define C0COMPILER_DEFUSECHAIN_H

//#include <algorithm>
#include <set>
#include "IR.h"
#include "../helper/Utils.h"



class DefUseChain {
public:
    class Node { // represent of one register.
    public:
        static int nextId;
        static vector<Node*> list;
        static map<IR*, Node*> ir2Node;
        int id;
        TmpVar* var;
        set<IR*> def;
        set<IR*> use;
        set<DefUseChain*> chains;

        Node(TmpVar* var):var(var){
            this->id = nextId;
            nextId++;
        }

        void addChain(DefUseChain* chain){
            chains.insert(chain);
            def.insert(chain->define);
            set<IR*>::const_iterator i=chain->use.begin();
            while(i!=chain->use.end()){
                IR* usage = (*i);
                use.insert(usage);
                i++;
            }
        }

        Node(DefUseChain* chain):var(chain->var){
            this->id = nextId;
            nextId++;
            def.insert(chain->define);
            set<IR*>::const_iterator i=chain->use.begin();
            while(i!=chain->use.end()){
                use.insert(*i);
                i++;
            }
            chains.insert(chain);
            if(ir2Node.count(chain->define)==0){
                ir2Node[chain->define] = this;
            }else{
                Error::nextErrorDetail<<"one Def can only belong to one Node: ";
                Error::internal(Error::Should_Not_Happen);
            }
        }

        bool conflict(Node* node){
            return (hasIntersection(this->def, node->use) ||
                    hasIntersection(this->use, node->def));
        }

        string toStringTight(){
            stringstream r;
            r << "["<< id << "]---------------------------------" << endl;

            set<IR*>::const_iterator i;
            for(i=def.begin(); i!=def.end(); i++){
                r << (*i)->id << " ";
            }
            r << "| ";
            for(i=use.begin(); i!=use.end(); i++){
                r << (*i)->id << " ";
            }
            r << endl;
            return r.str();
        }

        string toString(){
            stringstream r;
            set<DefUseChain*>::const_iterator i=chains.begin();
            r << "["<< id << "]---------------------------------" << endl;
            while(i!=chains.end()){
                r << (*i)->toString() << endl;
                i++;
            }
            return r.str();
        }

        static void printAll(){
            stringstream r;
            vector<Node*>::const_iterator i=list.begin();
            r << "Node/Web/Net List ######################" << endl;
            while(i!=list.end()){
//                r << (*i)->toString();
                r << (*i)->toStringTight();
                i++;
            }
            r << "########################################" << endl;
            cout << r.str();
        }


    };


    TmpVar* var;
    IR* define;
    set<IR*> use;

    static map<TmpVar*, set<DefUseChain*>> groupByVar;
    static map<IR*, DefUseChain*> irMap;

    static DefUseChain* getByDef(IR* ir){
        if(irMap.count(ir)>0){
            return irMap[ir];
        }else{
            Error::nextErrorDetail<<"defUseChain not found for IR: " << ir->print();
            Error::internal(Error::Should_Not_Happen);
        }
    }

    static DefUseChain* addUsage(IR* def, IR* use){
        DefUseChain* chain;
        if(irMap.count(def)==0){
            chain = new DefUseChain();
            chain->define = def;
            chain->var = def->result;
            irMap[def] = chain;
            groupByVar[chain->var].insert(chain);
            chain->use.insert(use);
        }else{
            chain = irMap[def];
            chain->use.insert(use);
        }
        return chain;
    }

    static void addUsage(vector<IR*>& defList, IR* use){
        unsigned long len = defList.size();
        if(len>0){
            for(int i=0; i<len; i++){
                DefUseChain::addUsage(defList[i], use);
            }
        }else{
            Error::nextErrorDetail<<"no definition found in IN set";
            Error::internal(Error::Should_Not_Happen);
        }
    }

    static void mergeChainToNode(){
        map<TmpVar*, set<DefUseChain*>>::const_iterator i = groupByVar.begin();
        while(i!=groupByVar.end()){
            TmpVar* var = (*i).first;
            vector<set<DefUseChain*>*> currentSets;
            set<DefUseChain*> chains = (*i).second;
            if(chains.size()>1){
                set<DefUseChain*>::const_iterator j = chains.begin();
                while(j!=chains.end()){
                    DefUseChain *chain = (*j);
                    addToCurrentOrNew(chain, currentSets);
                    j++;
                }
                for(int k=0; k<currentSets.size(); k++){
                    Node* node=new Node(var);
                    set<DefUseChain*> &chainsMerged = (*(currentSets[k]));
                    set<DefUseChain*>::const_iterator p=chainsMerged.begin();
                    while(p!=chainsMerged.end()){
                        DefUseChain* chain = (*p);
                        node->addChain(chain);
                        p++;
                    }
                    Node::list.push_back(node);
                }
            }else if(chains.size()==1){
                DefUseChain *chain = (*(chains.begin()));
                Node::list.push_back(new Node(chain));
            }
            i++;
        }
    }

    static void addToCurrentOrNew(DefUseChain* chain, vector<set<DefUseChain*>*> &currentSets){
        set<IR*> &usage = chain->use;
        vector<set<DefUseChain*>*>::const_iterator i = currentSets.begin();
        while(i!=currentSets.end()){
            set<DefUseChain*>* cur = (*i);
            set<DefUseChain*>::const_iterator j = cur->begin();
            while(j!=cur->end()){
                if(hasIntersection((*j)->use, usage)){
                    cur->insert(chain);
                    return;
                }
                j++;
            }
            i++;
        }
        set<DefUseChain*>* newSet = new set<DefUseChain*>();
        newSet->insert(chain);
        currentSets.push_back(newSet);
    }

    static bool hasIntersection(set<IR*> &s0, set<IR*> &s1){
        set<IR*> *smallerSet, *largerSet;
        if(s1.size()<s0.size()){
            smallerSet = &s1;
            largerSet = &s0;
        }else{
            smallerSet = &s0;
            largerSet = &s1;
        }
        set<IR*>::const_iterator i = smallerSet->begin();
        while(i!=smallerSet->end()){
            if(largerSet->count(*i)>0){
                return true;
            }
            i++;
        }
        return false;
//        vector<IR*> result;
//        set_intersection(s0.begin(), s0.end(),
//                         s1.begin(), s1.end(),
//                         std::back_inserter(result));
//        return result.size()>0;
    }

    static void printAll(){
        map<IR*, DefUseChain*>::const_iterator iter=irMap.begin();
        while(iter!=irMap.end()){
            cout << (*iter)
                    .second->toString();
            iter++;
        }
    }

    string toString(){
        stringstream r;
        r << var->name() << ": ";
        r << define->id << "| ";
//        r << define->toString(false) << " ===";
        set<IR*>::const_iterator iter=use.begin();
        while(iter!=use.end()){
            r <<  (*iter)->id << " ";
//            r << "|~~~  " << (*iter)->toString(false) << " ~~~";
            iter++;
        }
        return r.str();
    }



};


#endif //C0COMPILER_DEFUSECHAIN_H
